Chomsky sugeriu quatro classes de gramáticas: Gramáticas Regulares (Tipo-3), Gramáticas Livre de Contexto (Tipo-2) , Gramáticas Sensíveis ao Contexto (Tipo-1) e Gramáticas Irrestritas (Tipo-0). Estas gramáticas geram as classes de linguagens regulares (LR), linguagens livres de contexto (LLC), linguagens sensíveis ao contexto (LSC) e linguagens recursivamente enumerável (LRE), respectivamente. A relação entre estas linguagens é mostrada na figura abaixo:

(LR Ì LLC Ì LSC Ì LRE)

Existe uma correspondência exata entre cada uma dessas classes de linguagens e classes particulares de modelos computacionais (máquinas). Em outras palavras, para cada linguagem Tipo-i na hierarquia de Chomsky existe uma classe de máquinas M reconhecedoras de linguagens Tipo-i. E para cada classe de máquinas M existe uma linguagem Tipo-i tal que todas as linguagens reconhecidas por M são do Tipo-i.